#include<stdio.h> 
#include<conio.h> 
#define SIZE 100 

void mergesort(int a[], int low, int high); 
void merging(int a[], int low, int mid, int high); 

int main() { 
    int a[SIZE], n, i; 
    printf("Enter the size of an array: "); 
    scanf("%d", &n); 
    printf("Enter the Array Elements:\n"); 
    for(i = 0; i < n; i++) { 
        scanf("%d", &a[i]); 
    } 
    printf("Before Sorting Array Elements:\n"); 
    for(i = 0; i < n; i++) { 
        printf("%d\n", a[i]); 
    } 
    mergesort(a, 0, n - 1); 
    printf("After Sorting Array Elements:\n"); 
    for(i = 0; i < n; i++) { 
        printf("%d\n", a[i]); 
    } 
}  

void mergesort(int a[], int low, int high) { 
    int mid; 
    if(low < high) { 
        mid = (low + high) / 2; 
        mergesort(a, low, mid); 
        mergesort(a, mid + 1, high); 
        merging(a, low, mid, high); 
    } 
} 

void merging(int a[], int low, int mid, int high) { 
    int i, j, k; 
    int c[SIZE]; 
    i = low; 
    j = mid + 1; 
    k = low; 
    while(i <= mid && j <= high) { 
        if(a[i] < a[j]) { 
            c[k] = a[i]; 
            i++; 
        } else { 
            c[k] = a[j]; 
            j++; 
        } 
        k++; 
    } 
    while(i <= mid) { 
        c[k] = a[i]; 
        i++; 
        k++; 
    } 
    while(j <= high) { 
        c[k] = a[j]; 
        j++; 
        k++; 
    } 
    for(i = low; i <= high; i++) { 
        a[i] = c[i]; 
    } 
}